"""
选择排序：
    概述：
        选择排序是一种简单的排序算法，它的工作原理是：
        1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
        2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
        3. 重复第二步，直到所有元素均排序完毕。
    推理过程：假定列表长度为5
        比较论数        每轮比较次数             谁（索引）和谁（索引）比较          外循环次数（i）        内循环次数（j）
        0               4                       0和1,0和2,0和3,0和4             0                    1-4
        1               3                       1和2,1和3,1和4                  1                    2-4
        2               2                       2和3,2和4                       2                    3-4
        3               1                       3和4                            3                    4

    时间复杂度：
        选择排序的时间复杂度是O(n^2)。
    空间复杂度：
        选择排序的空间复杂度是O(1)。
    稳定性：不稳定
"""
# 1: 定义函数，select_sort(my_list)
def select_sort(my_list):
    # 1.1: 获取列表的长度
    n = len(my_list)
    # 1.2: 外层循环，比较的总轮数
    for i in range(n-1):
        # 定义最小值的索引。
        min_index = i
        # 1.2: 内循环，每轮比较的次数
        for j in range(i+1, n):
            # 1.3: 谁（索引）和谁（索引）比较, 如果当前元素比min_index对应的元素值小，就更新min_index
            if my_list[j] < my_list[min_index]:
                min_index = j

        # 1.4：走到治理，说明1轮的比较完毕，要看min_index和i是不是同一个元素
        if min_index != i:
            # 1.5：如果不是同一个元素，就交换位置
            my_list[i], my_list[min_index] = my_list[min_index], my_list[i]

if __name__ == '__main__':
    my_list = [5, 4, 1, 2, 3]
    print("排序前：", my_list)
    select_sort(my_list)
    print("排序后：", my_list)
